package com.wuxuan.algorithm_homework.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 拓扑排序
 * 主要用于有向无环图(DAG)，它能将图中所有顶点排成一个线性序列，
 * 使得对于图中的任意有向边(u, v)，顶点 u在序列中都出现在顶点 v之前。
 *
 *
 *
 * 算法原理
 * Kahn 算法(基于入度的算法)
 * 1.计算入度:首先，计算图中每个顶点的入度(即指向该顶点的边的数量)。
 * 2.初始化队列:将所有入度为 0的顶点加入一个队列。
 * 3.循环处理队列:
 * 从队列中取出一个顶点，并将其加入拓扑排序的结果序列中。
 * 遍历该顶点的所有出边，将这些出边所指向的顶点的入度减 1。。
 * 如果某个顶点的入度减为 0，则将其加入队列。
 *
 * 检查结果:如果最终拓扑排序的结果序列中的顶点数量等于图中的顶点数量，则说明图是有向无环图，且得到4.
 * 了一个有效的拓扑排序;否则，说明图中存在环，无法进行拓扑排序。
 */
public class TopologicalSortDemo {

    /**
     * 课程表
     * 现在你总共有 numcourses 门课需要选，记为0到 numcourses-1。
     * 给你一个数组 prerequisites ，其中 prerequisites[i]=[a(i)，b(i)]，
     * 表示在选修课程 a(i)前必须先选修 b(i)。
     *
     * 例如，想要学习课程 0，你需要先完成课程1，
     * 我们用一个匹配来表示:[0,1]返回你为了学完所有课程所安排的学习顺序。
     * 可能会有多个正确的顺序，你只要返回 任意一种 就可以了。
     * 如果不可能完成所有课程，返回 一个空数组。
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {
        //初始化
        List<Integer> result = new ArrayList<>();
        if (numCourses <= 0) {
            return result;
        }

        // 存储顶点的入度
        int[] indegree = new int[numCourses];

        // 存储图的邻接表
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new LinkedList<>());
        }

        // 构建邻接表和入度数组
//        邻接表：每个节点存储一个列表，表示 从该顶点出发的 所有边。
//        入度数组：每个节点存储一个值，表示指向该节点的边的数量。
        for (int[] prerequisite : prerequisites) {
            adjList.get(prerequisite[1]).add(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }

        //初始化队列
        Queue<Integer> queue = new LinkedList<>();
        //将入度为0的加入队列(先进先出)
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        //循环处理队列，以及存储结果
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            //一移出队列就将其存储到结果中
            result.add(vertex);
            //将需要在vertex优先出现之后的顶点的入度数-1,因此遍历邻接表，查看从vertex顶点出发的所有顶点值
            for (int i : adjList.get(vertex)) {
                indegree[i]--;
                //当有顶点度数减为0时，将其加入队列
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }
        }
        return result.size() == numCourses ? result : new ArrayList<>();
    }

    public static void main(String[] args) {
        TopologicalSortDemo test = new TopologicalSortDemo();
        System.out.println(test.topologicalSort(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}}));
    }

}
